import numpy as np
import quantecon.game_theory as gt
In our module, a normal form game and a player are represented by the classes NormalFormGame and Player, respectively.
A Player carries the player’s payoff function and implements in particular a method that returns the best response action(s) given an action of the opponent player, or a profile of actions of the opponents if there are more than one.
A NormalFormGame is in effect a container of Player instances.
matching_pennies_bimatrix = [[(1, -1), (-1, 1)],
[(-1, 1), (1, -1)]]
g_MP = gt.NormalFormGame(matching_pennies_bimatrix)
print(g_MP)
print("Player Instance; \n",g_MP.players[1]) # Player instance for player 1
print("Player 1's payoff array\n",g_MP.players[1].payoff_array) # Player 1's payoff array
print("payoff profile for action profile (0, 0)\n",g_MP[0, 0]) # payoff profile for action profile (0, 0)
2-player NormalFormGame with payoff profile array:
[[[ 1, -1], [-1, 1]],
[[-1, 1], [ 1, -1]]]
Player Instance;
Player in a 2-player normal form game with payoff array:
[[-1, 1],
[ 1, -1]]
Player 1's payoff array
[[-1 1]
[ 1 -1]]
payoff profile for action profile (0, 0)
[ 1 -1]
The game_theory module also supports games with more than two players.
Let us consider the following version of N -player Cournot Game.
from quantecon import cartesian
def cournot(a, c, N, q_grid):
"""
Create a `NormalFormGame` instance for the symmetric N-player Cournot game
with linear inverse demand a - Q and constant marginal cost c.
Parameters
----------
a : scalar
Intercept of the demand curve
c : scalar
Common constant marginal cost
N : scalar(int)
Number of firms
q_grid : array_like(scalar)
Array containing the set of possible quantities
Returns
-------
NormalFormGame
NormalFormGame instance representing the Cournot game
"""
q_grid = np.asarray(q_grid)
payoff_array = \
cartesian([q_grid]*N).sum(axis=-1).reshape([len(q_grid)]*N) * (-1) + \
(a - c)
payoff_array *= q_grid.reshape([len(q_grid)] + [1]*(N-1))
payoff_array += 0 # To get rid of the minus sign of -0
player = gt.Player(payoff_array)
return gt.NormalFormGame([player for i in range(N)])
Here’s a simple example with three firms, marginal cost 20, and inverse demand function 80−Q, where the feasible quantity values are assumed to be 10 and 15.
a, c = 80, 20
N = 3
q_grid = [10, 15] # [1/3 of Monopoly quantity, Nash equilibrium quantity]
g_Cou = cournot(a, c, N, q_grid)
print(g_Cou)
3-player NormalFormGame with payoff profile array:
[[[[300, 300, 300], [250, 250, 375]],
[[250, 375, 250], [200, 300, 300]]],
[[[375, 250, 250], [300, 200, 300]],
[[300, 300, 200], [225, 225, 225]]]]
Finding Nash equilibria
There are several algorithms implemented to compute Nash equilibria:
Brute force Find all pure-action Nash equilibria of an N player game (if any). Sequential best response Find one pure-action Nash equilibrium of an N player game (if any). Support enumeration Find all mixed-action Nash equilibria of a two-player nondegenerate game. Vertex enumeration Find all mixed-action Nash equilibria of a two-player nondegenerate game. Lemke-Howson Find one mixed-action Nash equilibrium of a two-player game. McLennan-Tourky Find one mixed-action Nash equilibrium of an N player game.
For more variety of algorithms, one should look at Gambit.
def print_pure_nash_brute(g):
"""
Print all pure Nash equilibria of a normal form game found by brute force.
Parameters
----------
g : NormalFormGame
"""
NEs = gt.pure_nash_brute(g)
num_NEs = len(NEs)
if num_NEs == 0:
msg = 'no pure Nash equilibrium'
elif num_NEs == 1:
msg = '1 pure Nash equilibrium:\n{0}'.format(NEs)
else:
msg = '{0} pure Nash equilibria:\n{1}'.format(num_NEs, NEs)
print('The game has ' + msg)
print_pure_nash_brute(g_Cou)
The game has 1 pure Nash equilibrium:
[(1, 1, 1)]
def sequential_best_response(g, init_actions=None, tie_breaking='smallest',
verbose=True):
"""
Find a pure Nash equilibrium of a normal form game by sequential best
response.
Parameters
----------
g : NormalFormGame
init_actions : array_like(int), optional(default=[0, ..., 0])
The initial action profile.
tie_breaking : {'smallest', 'random'}, optional(default='smallest')
verbose: bool, optional(default=True)
If True, print the intermediate process.
"""
N = g.N # Number of players
a = np.empty(N, dtype=int) # Action profile
if init_actions is None:
init_actions = [0] * N
a[:] = init_actions
if verbose:
print('init_actions: {0}'.format(a))
new_a = np.empty(N, dtype=int)
max_iter = np.prod(g.nums_actions)
for t in range(max_iter):
new_a[:] = a
for i, player in enumerate(g.players):
if N == 2:
a_except_i = new_a[1-i]
else:
a_except_i = new_a[np.arange(i+1, i+N) % N]
new_a[i] = player.best_response(a_except_i,
tie_breaking=tie_breaking)
if verbose:
print('player {0}: {1}'.format(i, new_a))
if np.array_equal(new_a, a):
return a
else:
a[:] = new_a
print('No pure Nash equilibrium found')
return None
A Cournot game with linear demand is known to be a potential game, for which sequential best response converges to a Nash equilibrium.
Let us try a bigger instance:
a, c = 80, 20
N = 3
q_grid = np.linspace(0, a-c, 13) # [0, 5, 10, ..., 60]
g_Cou = cournot(a, c, N, q_grid)
a_star = sequential_best_response(g_Cou) # By default, start with (0, 0, 0)
print('Nash equilibrium indices: {0}'.format(a_star))
print('Nash equilibrium quantities: {0}'.format(q_grid[a_star]))
init_actions: [0 0 0]
player 0: [6 0 0]
player 1: [6 3 0]
player 2: [6 3 1]
player 0: [4 3 1]
player 1: [4 3 1]
player 2: [4 3 2]
player 0: [3 3 2]
player 1: [3 3 2]
player 2: [3 3 3]
player 0: [3 3 3]
player 1: [3 3 3]
player 2: [3 3 3]
Nash equilibrium indices: [3 3 3]
Nash equilibrium quantities: [15. 15. 15.]
# Start with the largest actions (12, 12, 12)
sequential_best_response(g_Cou, init_actions=(12, 12, 12))
init_actions: [12 12 12]
player 0: [ 0 12 12]
player 1: [ 0 0 12]
player 2: [0 0 6]
player 0: [3 0 6]
player 1: [3 1 6]
player 2: [3 1 4]
player 0: [3 1 4]
player 1: [3 2 4]
player 2: [3 2 3]
player 0: [3 2 3]
player 1: [3 3 3]
player 2: [3 3 3]
player 0: [3 3 3]
player 1: [3 3 3]
player 2: [3 3 3]
array([3, 3, 3])
# The limit action profile is indeed a Nash equilibrium:
g_Cou.is_nash(a_star)
True
# In fact, the game has other Nash equilibria (because of our choice of grid points and parameter values):
print_pure_nash_brute(g_Cou)
The game has 7 pure Nash equilibria:
[(2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 3, 3), (3, 4, 2), (4, 2, 3), (4, 3, 2)]
Next, let us study the All-Pay Acution, where, unlike standard auctions, bidders pay their bids regardless of whether or not they win. Situations modeled as all-pay auctions include job promotion, R&D, and rent seeking competitions, among others.
Here we consider a version of All-Pay Auction with complete information, symmetric bidders, discrete bids, bid caps, and “full dissipation” (where the prize is materialized if and only if there is only one bidder who makes a highest bid).
from numba import jit
def all_pay_auction(r, c, N, dissipation=True):
"""
Create a `NormalFormGame` instance for the symmetric N-player
All-Pay Auction game with common reward `r` and common bid cap `e`.
Parameters
----------
r : scalar(float)
Common reward value.
c : scalar(int)
Common bid cap.
N : scalar(int)
Number of players.
dissipation : bool, optional(default=True)
If True, the prize fully dissipates in case of a tie. If False,
the prize is equally split among the highest bidders (or given
to one of the highest bidders with equal probabilities).
Returns
-------
NormalFormGame
NormalFormGame instance representing the All-Pay Auction game.
"""
player = gt.Player(np.empty((c+1,)*N))
populate_APA_payoff_array(r, dissipation, player.payoff_array)
return gt.NormalFormGame((player,)*N)
@jit(nopython=True)
def populate_APA_payoff_array(r, dissipation, out):
"""
Populate the payoff array for a player in an N-player All-Pay
Auction game.
Parameters
----------
r : scalar(float)
Reward value.
dissipation : bool, optional(default=True)
If True, the prize fully dissipates in case of a tie. If False,
the prize is equally split among the highest bidders (or given
to one of the highest bidders with equal probabilities).
out : ndarray(float, ndim=N)
NumPy array to store the payoffs. Modified in place.
Returns
-------
out : ndarray(float, ndim=N)
View of `out`.
"""
nums_actions = out.shape
N = out.ndim
for bids in np.ndindex(nums_actions):
out[bids] = -bids[0]
num_ties = 1
for j in range(1, N):
if bids[j] > bids[0]:
num_ties = 0
break
elif bids[j] == bids[0]:
if dissipation:
num_ties = 0
break
else:
num_ties += 1
if num_ties > 0:
out[bids] += r / num_ties
return out
# Consider the two-player case with the following parameter values:
N = 2
c = 5 # odd
r = 8
g_APA_odd = all_pay_auction(r, c, N)
print(g_APA_odd)
2-player NormalFormGame with payoff profile array:
[[[ 0., 0.], [ 0., 7.], [ 0., 6.], [ 0., 5.], [ 0., 4.], [ 0., 3.]],
[[ 7., 0.], [-1., -1.], [-1., 6.], [-1., 5.], [-1., 4.], [-1., 3.]],
[[ 6., 0.], [ 6., -1.], [-2., -2.], [-2., 5.], [-2., 4.], [-2., 3.]],
[[ 5., 0.], [ 5., -1.], [ 5., -2.], [-3., -3.], [-3., 4.], [-3., 3.]],
[[ 4., 0.], [ 4., -1.], [ 4., -2.], [ 4., -3.], [-4., -4.], [-4., 3.]],
[[ 3., 0.], [ 3., -1.], [ 3., -2.], [ 3., -3.], [ 3., -4.], [-5., -5.]]]
## no pure nash
gt.pure_nash_brute(g_APA_odd)
[]
As pointed out by Dechenaux et al. (2006), there are three Nash equilibria when the bid cap c is odd (so that there are an even number of actions for each player):
gt.support_enumeration(g_APA_odd)
[(array([0.5 , 0. , 0.25, 0. , 0.25, 0. ]),
array([0. , 0.25, 0. , 0.25, 0. , 0.5 ])),
(array([0. , 0.25, 0. , 0.25, 0. , 0.5 ]),
array([0.5 , 0. , 0.25, 0. , 0.25, 0. ])),
(array([0.125, 0.125, 0.125, 0.125, 0.125, 0.375]),
array([0.125, 0.125, 0.125, 0.125, 0.125, 0.375]))]
c = 6 # even
g_APA_even = all_pay_auction(r, c, N)
gt.support_enumeration(g_APA_even)
[(array([0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.25 ]),
array([0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.25 ]))]